package Ali;

/**
 * 给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。
 * 输入：nums = [3,6,5,1,8]
 * 输出：18
 * 解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）.
 * @author le
 */
public class Test35
{
    public static void main(String[] args)
    {

    }

    public int maxSumDivThree(int[] nums) {
        int len = nums.length;
        int[][] dp = new int[len+1][3];

        dp[0][0] = 0;
        dp[0][1] = Integer.MIN_VALUE;
        dp[0][2] = Integer.MIN_VALUE;

        for (int i = 1;i <= len;i++){
            if (nums[i-1] % 3 == 0){
                dp[i][0] = Math.max(dp[i-1][0],dp[i-1][0]+nums[i-1]);
                dp[i][1] = Math.max(dp[i-1][1],dp[i-1][1]+nums[i-1]);
                dp[i][2] = Math.max(dp[i-1][2],dp[i-1][2]+nums[i-1]);
            }

            if (nums[i-1] % 3 == 2){
                dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+nums[i-1]);
                dp[i][1] = Math.max(dp[i-1][1],dp[i-1][2]+nums[i-1]);
                dp[i][2] = Math.max(dp[i-1][2],dp[i-1][0]+nums[i-1]);
            }

            if (nums[i-1] % 3 == 1){
                dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]+nums[i-1]);
                dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+nums[i-1]);
                dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]+nums[i-1]);
            }
        }

        return dp[len][0];
    }
}
